On Comparing Two Structured RNA Multiple alignments.

Proceedings of the ACM SIGMOD International Conference on Management of Data

Bioinformatic Databases.

Detecting conserved secondary structures in RNA molecules using constrained structural alignment.
journal homepage: www.elsevier.com/locate/compbiolchem
Discovering Frequent Agreement Subtrees from Phylogenetic Data.
Abstract—We study a new data mining problem concerning the discovery of frequent agreement subtrees (FASTs) from a set of phylogenetic trees. A phylogenetic tree, or phylogeny, is an unordered tree in which the order among siblings is unimportant. Furthermore, each leaf in the tree has a label representing a taxon (species or organism) name, whereas internal nodes are unlabeled. The tree may have a root, representing the common ancestor of all species in the tree, or may be unrooted. An unrooted phylogeny arises due to the lack of sufficient evidence to infer a common ancestor of the taxa in the tree. The FAST problem addressed here is a natural extension of the maximum agreement subtree (MAST) problem widely studied in the computational phylogenetics community. The paper establishes a framework for tackling the FAST problem for both rooted and unrooted phylogenetic trees using data mining techniques. We first develop a novel canonical form for rooted trees together with a phylogeny-aware tree expansion scheme for generating candidate subtrees level by level. Then, we present an efficient algorithm to find all FASTs in a given set of rooted trees, through an Apriori-like approach. We show the correctness and completeness of the proposed method. Finally, we discuss the extensions of the techniques to unrooted trees. Experimental results demonstrate that the proposed methods work well, and are capable of finding interesting patterns in both synthetic data and real phylogenetic trees. Index Terms—Data mining, evolutionary bioinformatics, computational phylogenetics, algorithmic design, pattern discovery. 1
Analysis of Biological Data A Soft Computing Approach

Constrained RNA Structural Alignment Algorithms and Application to Motif Detection in the Untranslated Regions of Trypanosoma brucei mRNAs.



Detecting Conserved RNA Secondary Structures in Viral Genomes The RADAR Approach.

Toward an Integrated RNA Motif Database.

A study of phylogenetic tools for genomic nomenclature data cleaning.

Classification of RNA Sequences with Support Vector Machines.

Biological data cleaning a case study.

RADAR a web server for RNA data analysis and research.

A New Kernel Method for RNA Classification.

RADAR An InteractiveWeb%2DBased Toolkit for RNA Data Analysis and Research.


Mining Frequent Agreement Subtrees in Phylogenetic Databases.


Kernel design for RNA classification using Support Vector Machines.

Data Mining in Bioinformatics
Bioinformatics, the study and application of computational methods to life sciences data, is presently enjoying a surge of interest. The main reason for this welcome publicity is the nearing completion of the sequencing of the human genome and the anticipation that the knowledge derived from this process will have a great impact on modern medicine. The pharmaceutical industry, which expects to utilize the knowledge for new drug design, has a particular interest in bioinformatics. The structure of data...
Biomonitoring%2C Phylogenetics and Anomaly Aggregation Systems.

Lineage Path Integration for Phylogenetic Resources.

Introduction to Data Mining in Bioinformatics.

A method for aligning RNA secondary structures and its application to RNA motif detection.

MetricMap an embedding technique for processing distance%2Dbased queries in metric spaces.
Abstract—In this paper, we present an embedding technique, called MetricMap, which is capable of estimating distances in a pseudometric space. Given a database of objects and a distance function for the objects, which is a pseudometric, we map the objects to vectors in a pseudo-Euclidean space with a reasonably low dimension while preserving the distance between two objects approximately. Such an embedding technique can be used as an approximate oracle to process a broad class of distance-based queries. It is also adaptable to data mining applications such as data clustering and classification. We present the theory underlying MetricMap and conduct experiments to compare MetricMap with other methods including MVP-tree and M-tree in processing the distance-based queries. Experimental results on both protein and RNA data show the good performance and the superiority of MetricMap over the other methods. Index Terms—Bioinformatics, data mining, embedding method, metric space, nearest neighbors, similarity search. I.
Xml Clustering And Retrieval Through Principal Component Analysis.

Unordered Tree Mining with Applications to Phylogeny.
Frequent structure mining (FSM) aims to discover and extract patterns frequently occurring in structural data, such as trees and graphs. FSM finds many applications in bioinformatics, XML processing, Web log analysis, and so on. In this paper we present a new FSM technique for finding patterns in rooted unordered labeled trees. The patterns of interest are cousin pairs in these trees. A cousin pair is a pair of nodes sharing the same parent, the same grandparent, or the same great-grandparent, etc. Given a tree, our algorithm finds all interesting cousin pairs of ¢
FlowMiner Finding Flow Patterns in Spatio%2DTemporal Databases.

XML Clustering by Principal Component Analysis.

GeneScout a data mining system for predicting vertebrate genes in genomic DNA sequences.

BIO%2DAJAX An Extensible Framework for Biological Data Cleaning.

Proceedings of the 3nd ACM SIGKDD Workshop on Data Mining in Bioinformatics %28BIOKDD 2003%29

Computational Biology and Genome Informatics
RNA profiling analysis and new techniques such as proteomics are yielding vast amounts of data on gene expression and protein levels. This points to the need to develop new methodologies to identify and analyze complex biological networks. This chapter describes the development of a Java-based tool that helps dynamically find and visualize metabolic networks. The tool consists of three parts. The first part is a text-mining tool that pulls out potential metabolic relationships from the PubMed database. These relationships are then reviewed by a domain expert and added to an existing network model. The result is visualized using an interactive graph display module. The basic metabolic or regulatory flow in the network is modeled using fuzzy cognitive maps. Causal connections are pulled out from sequence data using a genetic algorithm-based logical proposition generator that searches for temporal patterns in microarray data. Examples from the regulatory and...
Opening Remarks.

TreeRank A Similarity Measure for Nearest Neighbor Searching in Phylogenetic Databases.
Phylogenetic trees are unordered labeled trees in which each leaf node has a label and the order among siblings is unimportant. In this paper we propose a new similarity measure, called TreeRank, for phylogenetic trees and present an algorithm for computing TreeRank scores. Given a query tree ¥ or pattern and a data tree, the TreeRank from ¥ to¦ score is a measure of the topological relationships that are found to be the same or similar. The proposed algorithm calculates in¥ the TreeRank score time where � is the in¦ number of nodes appearing both ¥ and¦ in and � , is the number of nodes. We then develop a search engine that, given a query or pattern in§©¨���������� and a database in¦ trees � of, finds and ranks the nearest of¥ tree¥ neighbors where the “nearness ” is measured by the proposed similarity function. This structure-based search engine is in� fully operational and is available on the World Wide Web. 1

Protein Classification A Geometric Hashing Approach.


Data mining in bioinformatics report on BIOKDD%2703.

Proceedings of the 2nd ACM SIGKDD Workshop on Data Mining in Bioinformatics %28BIOKDD 2002%29

Clustering and Classifying Enzymes in Metabolic Pathways Some Preliminary Results.

Foreword.
reference set of international guidelines and recommendations for the reporting and presentation of statistical data and metadata. Although, the Handbook was prepared primarily for short-term economic statistics, many, if not most of the recommendations presented are also relevant for annual (structural) statistics and for social and population statistics. The Handbook draws heavily on existing international statistical guidelines and recommendations that have been developed over the last twenty years by international organisations and national statistical agencies. These international standards have been developed for implementation by international organisations themselves and by national agencies in both developed and developing economies. The need for the articulation of a comprehensive set of recommendations on the reporting and presentation of statistical data and metadata is one aspect of the overall demand for improved international comparability and consistency of statistics compiled and published by national agencies and international organisations. This requirement has itself been driven by closer economic and social linkages between both the 30 OECD Member countries and between those countries and large emerging non-member economies. As discussed in the Handbook, the major causes of differences in statistics compiled in different countries flow from the use of different definitions and concepts and
Mining Genes in DNA Using GeneScout.

Algorithmics and Applications of Tree and Graph Searching.
Modern search engines answer keyword-based queries extremely efficiently. The impressive speed is due to clever inverted index structures, caching, a domain-independent knowledge of strings, and thousands of machines. Several research efforts have attempted to generalize keyword search to keytree and keygraph searching, because trees and graphs have many applications in next-generation database systems. This paper surveys both algorithms and applications, giving some emphasis to our own work.
A Structure%2DBased Search Engine for Phylogenetic Databases.

ATreeGrep Approximate Searching in Unordered Trees.
An unordered labeled tree is a tree in which each node has a string label and the parent-child relationship is significant, but the order among siblings is unimportant. This paper presents an approach...
Finding Patterns in Three%2DDimensional Graphs Algorithms and Applications to Scientific Data Mining.
This paper presents a method for finding patterns in three dimensional (3D) graphs. Each node  in a graph is an undecomposable or atomic unit and has a label. Edges are links between the atomic  units. Patterns are rigid substructures that may occur in a graph after allowing for an arbitrary  number of whole-structure rotations and translations as well as a small number (specified by the user)  of edit operations in the patterns or in the graph. (When a pattern appears in a graph only after the  graph has been modified, we call that appearance &#034;approximate occurrence.&#034;) The edit operations  include relabeling a node, deleting a node and inserting a node. The proposed method is based on the  geometric hashing technique, which hashes node-triplets of the graphs into a 3D table and compresses  the label-triplets in the table. To demonstrate the utility of our algorithms, we discuss two applications  of them in scientific data mining.
XML Query by Example.

Finding approximate patterns in undirected acyclic graphs.
We consider an approximate pattern matching problem for undirected acyclic graphs. Specifically, let P be a pattern graph, D a data graph and t an integer. We present an algorithm to locate a subgraph in D whose distance from P is at most t. The distance measure used here is the degree-2 metric published previously. The time complexity of our algorithm is O(N_P N_D d &amp;radic;d log d) where N_P and N_D are the number of nodes in P and D, respectively; d = min{d_P, d_D}; d_P and d_D are the maximum degree of P and D, respectively. Central to our algorithm is a procedure for finding approximate patterns in rooted unordered trees and freely allowing cuts. We discuss two...
BIOKDD01 Workshop on Data Mining in Bioinformatics.

BIOKDD 2002 Recent Advanced in Data Minig for Bioinformatics.

Proceedings of the ACM SIGKDD Workshop on Data Mining in Bioinformatics %28BIOKDD 2001%29

Mining the World Wide Web An Information Search Approach

New techniques for extracting features from protein sequences.
In this paper we propose new techniques to extract features from protein sequences. We then use the features as inputs for a Bayesian neural network (BNN) and apply the BNN to classifying protein sequences obtained from the PIR protein database maintained at the National Biomedical Research Foundation. To evaluate the performance of the proposed approach, we compare it with other protein classiers built based on sequence alignment and machine learning methods. Experimental results show the high precision of the proposed classi er and the complementarity of the bioinformatics tools studied in the paper.
DNA sequence classification via an expectation maximization algorithm and neural networks a case study.
This paper presents new techniques for biosequence classification, with a focus on recognizing E. Coli promoters in DNA. Specifically, given an unlabeled DNA sequence S, we want to determine whether or not S is an E. Coli promoter. We use an expectation-maximization (EM) algorithm to locate the-35 and-10 binding sites in an E. Coli promoter sequence. The EM algorithm differs from previously published EM algorithms in that, instead of assuming a uniform distribution for the lengths of the spacer between the-35 binding site and the-10 binding site as well as the spacer between the-10 binding site and the transcriptional start site, our algorithm deduces the probability distribution for these lengths. Based on the located binding sites, we select features in each E. Coli promoter sequence according to their information contents and represent the features using an orthogonal encoding method. We then feed the features to a neural network for promoter recognition. Empirical studies show that the proposed approach achieves good performance on different datasets.
Bioinformatics %2D Introduction to the Special Issue.

Effective hidden Markov models for detecting splicing junction sites in DNA sequences.

Precise Environmental Searches Integrating Hierarchical Information Search with EnviroDaemon.
Information retrieval has evolved from searches of references, to abstracts, to documents. Search on the Web involves search engines that promise to parse full-text and other files: audio, video, and multimedia. With the indexable Web at 320 million pages and growing, difficulties with locating relevant information have become apparent. The most prevalent means for information retrieval relies on syntax-based methods: keywords or strings of characters are presented to a search engine, and it returns all the matches in the available documents. This method is satisfactory and easy to implement, but it has some inherent limitations that make it unsuitable for many tasks. Instead of looking for syntactical patterns, the user often is interested in keyword meaning or the location of a particular word in a title or header. This paper describes some precise search approaches in the environmental domain that locate information according to syntactic criteria, augmented by the utilization of information in a certain context. The main emphasis of this paper lies in the treatment of structured knowledge, where essential aspects about the topic of interest are encoded not only by the individual items, but also by their relationships among each other. Examples for such structured knowledge are hypertext documents, diagrams, logical and chemical formulae. Benefits of this approach are enhanced precision and approximate search in an already focused, context-specific search engine for the environment: EnviroDaemon.
Finding similar consensus between trees an algorithm and a distance hierarchy.

Application of neural networks to biological data mining a case study in protein sequence classification.
Biological data mining aims to extract significant information from DNA, RNA and proteins. The significant information may refer to motifs, functional sites, clustering and classification rules. This paper presents an example of biological data mining: the classification of protein sequences using neural networks. We propose new techniques to extract features from protein data and use them in combination with the Bayesian neural network to classify protein sequences obtained from the PIR protein database maintained at the National Biomedical Research Foundation. To evaluate the performance of the proposed approach, we compare it with other protein classifiers built based on sequence alignment and machine learning methods. Experimental results show the high precision of the proposed classifier and the complementarity of the tools studied in the paper.  Keywords  Bioinformatics, biological data mining, machine learning, neural networks, sequence alignment, feature extraction from  protei...
An Approximate Search Engine for Structural Databases.

Identifying consensus of trees through alignment.

Fast Similarity Search in Three%2DDimensional Structure Databases.
this paper we study the similarity search problem and a class of related queries.
An Index Structure for Data Mining and Clustering.
Abstract. In this paper we present an index structure, called Metric-Map, that takes a set of objects and a distance metric and then maps those objects to a k-dimensional space in such away that the distances among objects are approximately preserved. The index structure is a useful tool for clustering and visualization in data intensive applications, because it replaces expensive distance calculations by sum-of-square calculations. This can make clustering in large databases with expensive distance metrics practical. We compare the index structure with another data mining index structure, FastMap, recently proposed by Faloutsos and Lin, according to two criteria: relative error and clustering accuracy. For relative error, we show that (i) F astMap gives a lower relative error than MetricMap for Euclidean distances, (ii) MetricMap gives alower relative error than F astMap for non-Euclidean distances (i.e., general distance metrics), and (iii) combining the two reduces the error yet further. A similar result is obtained when comparing the accuracy of
Pattern Discovery in Biomolecular Data Tools%2C Techniques and Applications

Application of Bayesian Neural Networks to Protein Sequence Classification.
In this paper we present an application of neural networks to biomedical data mining. Specifically we propose a hybrid approach, combining similarity search and Bayesian neural networks, to classify protein sequences. We apply our techniques to recognizing the globin sequences obtained from the database maintained in the Protein Information Resources (PIR) at the National Biomedical Research Foundation. Experimental results indicate an excellent performance of the proposed approach.  Keywords: Artificial intelligence, biomedical applications, data mining, machine learning. 1 Introduction  Data mining or knowledge discovery in data (KDD) is aimed to find significant information from a set of data [8]. The knowledge to be mined from the dataset may refer to patterns, association rules, belief networks, classification and clustering regulations, and so forth. The techniques used to mine the knowledge are borrowed from many disciplines, including pattern recognition, machine learning, gene...
Evaluating a Class of Distance%2DMapping Algorithms for Data Mining and Clustering.
A distance-mapping algorithm takes a set of objects and a distance metric and then maps those objects to a Euclidean or pseudo-Euclidean space in such a way that the distances among objects are approximately preserved. Distancemapping algorithms are a useful tool for clustering and visualization in data intensive applications, because they replace expensive distance calculations by sum-of-square calculations. This can make clustering in large databases with expensive distance metrics practical.  In this paper we present five distance-mapping algorithms and conduct experiments to compare their performance in data clustering applications. These include two algorithms called FastMap and MetricMap, and three hybrid heuristics that combine the two algorithms in different ways. Experimental results on both synthetic and RNA data show the superiority of the hybrid algorithms. The results imply that FastMap and MetricMap capture complementary information about distance metrics and therefore ca...
A Framework for Biological Pattern Discovery on Networks of Workstations.

Pattern Discovery and Classification in Biosequences.


Identifying Approximately Common Substructures in Trees Based on a Restricted Edit Distance.

Biocomputing %2D Introduction to the Special Issue.


New Techniques for DNA Sequence Classification.
DNA sequence classification is the activity of determining whether or not an unlabeled sequence S belongs to an existing class C. This paper proposes two new techniques for DNA sequence classification. The first technique works by comparing the unlabeled sequence S with a group of active motifs discovered from the elements of C and by distinction with elements outside of C. The second technique generates and matches gapped fingerprints of S with elements of C. Experimental results obtained by running these algorithms on long and well conserved Alu sequences demonstrate the good performance of the presented methods compared with FASTA. When applied to less conserved and relatively short functional sites such as splice-junctions, a variation of the second technique combining fingerprinting with consensus sequence analysis gives better results than the current classifiers employing text compression and machine learning algorithms.  2  INTRODUCTION  DNA sequence classification is an import...
An Approximate Oracle for Distance in Metric Spaces.

An Algorithm for Finding the Largest Approximately Common Substructures of Two Trees.
Ordered, labeled trees are trees in which each node has a label and the left-to-right  order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern  recognition, molecular biology and natural language processing. We consider a substructure of an  ordered labeled tree T to be a connected subgraph of T . Given two ordered labeled trees T1 and T2  and an integer d, the largest approximately common substructure problem is to find a substructure  U1 of T1 and a substructure U2 of T2 such that U1 is within edit distance d of U2 and where there  does not exist any other substructure V1 of T1 and V2 of T2 such that V1 and V2 satisfy the distance  constraint and the sum of the sizes of V1 and V2 is greater than the sum of the sizes of U1 and  U2 . We present a dynamic programming algorithm to solve this problem, which runs as fast as the  fastest known algorithm for computing the edit distance of two trees when the distance allowed  in the common substruc...
Scientific Data Mining A Case Study.

A graphical environment for change detection in structured documents.

Electronic enterprise engineering an outline of an architecture.
In this paper we put forth a vision for organiza-tions to fully embmce computer support. We propose a business-process oriented architecture for Electronic Enterprise Engineering (EEE) that will enable enter-prises to manage and evolve all technological and orga-nizational processes efectively; integrate and manage all enterprise information electronically; and empower knowledge workers at all levels with broad decision sup-port Capabilities. Our goal is for the EEE architecture to empower an enterprise to make the best use of its in-formational assets to operate efectively in thaS new era of electronic commerce. As part of this project we are developing a standard-based, customizable, integrated tool set called the Support Environment for Enterprise Engineering (SEEE). This paper presents the current SEEE architecture and shows how it supports the three EEE goals. 1. SEEE: An architecture for EEE The drive towards electronic commerce is pushing companies to move more and more of their opera-tions on-line.Organizations must deal with clients and customers on-line, handle telecommuting and work-groups distributed moss the country or world-wide, deal with government agencies and other organizations with whom they have relations on-line, and so on. Certainly many companies have moved some mission-critical portions of their operations on-line, and many
Fast retrieval of electronic messages that contain mistyped words or spelling errors.
Abstract—This paper presents an index structure for retrieving electronic messages that contain mistyped words or spelling errors. Given a query string (e.g., a search key), we want to find those messages that approximately contain the query, i.e., certain inserts, deletes and mismatches are allowed when matching the query with a word (or phrase) in the messages. Our approach is to store the messages sequentially in a database and hash their “fingerprints ” into a number of “fingerprint files. ” When the query is given, its fingerprints are also hashed into the files and a histogram of votes is constructed on the messages. We derive a lower bound, based on which one can prune a large number of nonqualifying messages (i.e., those whose votes are below the lower bound) during searching. The paper presents some experimental results, which demonstrate the effectiveness of the index structure and the lower bound. I.
Scientific Data Classification A Case Study.

Automated Discovery of Active Motifs in Three Dimensional Molecules.
In this paper we present a method for discovering  approximately common motifs (also known as active  motifs) in three dimensional (3D) molecules.  Each node in a molecule is represented by a 3D  point in the Euclidean Space and each edge is represented  by an undirected line segment connecting  two nodes in the molecule. Motifs are rigid  substructures which may occur in a molecule after  allowing for an arbitrary number of rotations  and translations as well as a small number (specified  by the user) of node insert/delete operations  in the motifs or the molecule. (We call this &#034;approximate  occurrence.&#034;) The proposed method  combines the geometric hashing technique and  block detection algorithms for undirected graphs.  To demonstrate the utility of our algorithms, we  discuss their applications to classifying three families  of molecules pertaining to antibacterial sulfa  drugs, anti-anxiety agents (benzodiazepines) and  antiadrenergic agents (fi receptors). Experimental  results i...
Structural Matching and Discovery in Document Databases.
This memo is being written to ... the SGML markup minimization ... .................................................. Although only one tag is visible in ... &#034;carbon copy&#034; recipient), the SGML ... Yours truly, ................................................ &lt;!doctype memo SYSTEM&gt; Fig. 2. An SGML memo document A. Charles F. Goldfarb
Fast retrieval of electronic messages that contain mistyped words or spelling errors.
Abstract—This paper presents an index structure for retrieving electronic messages that contain mistyped words or spelling errors. Given a query string (e.g., a search key), we want to find those messages that approximately contain the query, i.e., certain inserts, deletes and mismatches are allowed when matching the query with a word (or phrase) in the messages. Our approach is to store the messages sequentially in a database and hash their “fingerprints ” into a number of “fingerprint files. ” When the query is given, its fingerprints are also hashed into the files and a histogram of votes is constructed on the messages. We derive a lower bound, based on which one can prune a large number of nonqualifying messages (i.e., those whose votes are below the lower bound) during searching. The paper presents some experimental results, which demonstrate the effectiveness of the index structure and the lower bound. I.
Knowledge Discovering for Document Classification Using Tree Matching in TEXPROS.

Automated Discovery of Active Motifs in Multiple RNA Secondary Structures.

Scientific Data Mining A Case Study.

A Visualization Tool for Pattern Matching and Discovery in Scientific Databases.
Sequence databases comprise sequence data, which are linear structural descriptions of many natural entities. Approximate pattern discovery in a sequence database can lead to important conclusions or prediction of new phenomena. Traditional database technology is not suitable for accomplishing the task, and new techniques need to be developed. In this dissertation, we propose several new techniques for discovering patterns in sequence databases. Our techniques incorporate pattern matching algorithms and novel heuristics for discovery and optimization. Experimental results of applying the techniques to both generated data and DNA/proteins show the effectiveness of the proposed techniques. We then develop several classifiers using our pattern discovery algorithms and a previously published fingerprint technique. When we apply the classifiers to classify DNA and protein seq...
Curriculum Knowledge Representation and Manipulation in Knowledge%2DBased Tutoring Systems.
Abstract-A Knowledge-Based Tutoring System (KBTS) is a computer-based instructional system that uses artificial intelligence techniques to help people learn some subjects. We found that the knowledge communication process involving a KBTS and a human student can be decomposed into a series of communication cycles, where each cycle concentrates on one topic and contains four major phases: planning, discussing, evaluating and remedying. The major contributions of this work are the development of a generic architecture for supporting the knowledge communication between a KBTS and a student, and a graphical notation and schema for supporting the curriculum knowledge representation and manipulation during the planning phase of a tutoring process. The curriculum knowledge about a course can help a tutoring system determine the sequences in which the topics will be discussed with the students effectively and diagnose the students ’ mistakes. The curriculclm knowledge base contains the goal structure of the course, prerequisite relations, and multiple ways of organizing topics, among others. As an example, we have focused on developing SQL-TUTOR, a KBTS for the domain of SQL programming. This system has features such as efficient control mechanism, explicit curriculum knowledge representation, and individualized private tutoring. For allowing the students relative freedom to decide how to study the domain knowledge about a subject, the system provides the students with a group of operators to hand-tailor the learning schedules according to their special backgrounds, requests, and interests. Index Terms4omputer in education, intelligent tutoring, knowledge representation and manipulation, topic association graph, learning graph, curriculum management.
Information Extraction from the Structured Part of Office Documents.

On the Editing Distance Between Undirected Acyclic Graphs.
We consider the problem of comparing CUAL graphs (Connected, Undirected, Acyclic graphs with nodes being Labeled). This problem is motivated by the study of information retrieval for bio-chemical and molecular databases. Suppose we define the distance between two CUAL graphs G1 and G2 to be the weighted number of edit operations (insert node, delete node and relabel node) to transform G1 to G2. By reduction from exact cover by 3-sets, one can show that finding the distance between two CUAL graphs is NP-complete. In view of the hardness of the problem, we propose a constrained distance metric, called the degree-2 distance, by requiring that any node to be inserted (deleted) have no more than 2 neighbors. With this metric, we present an efficient algorithm to solve the problem. The algorithm runs in time O(N_1 N_2 D&amp;sup2;) for general weighting edit operations and in time O(N_1 N_2 D &amp;radic;D log D) for integral weighting edit operations, where N_i, i = 1, 2, is the number of nodes in G_i, D = min{d_1, d_2} and d_i is the maximum degree of G_i.
LHM a logic%2Dbased hypertext data model for integrating hypertext and information systems.

On the Editing Distance between Undirected Acyclic Graphs and Related Problems.

LHM a logic%2Dbased hypertext data model for integrating hypertext and information systems.

An Integrated Toolkit for Pattern Matching and Pattern Discovery in Scientific
Sequence databases comprise sequence data, which are linear structural descriptions of many natural entities. Approximate pattern discovery in a sequence database can lead to important conclusions or prediction of new phenomena. Traditional database technology is not suitable for accomplishing the task, and new techniques need to be developed. In this dissertation, we propose several new techniques for discovering patterns in sequence databases. Our techniques incorporate pattern matching algorithms and novel heuristics for discovery and optimization. Experimental results of applying the techniques to both generated data and DNA/proteins show the effectiveness of the proposed techniques. We then develop several classifiers using our pattern discovery algorithms and a previously published fingerprint technique. When we apply the classifiers to classify DNA and protein seq...
Pattern Matching and Pattern Discovery in Scientific
Sequence databases comprise sequence data, which are linear structural descriptions of many natural entities. Approximate pattern discovery in a sequence database can lead to important conclusions or prediction of new phenomena. Traditional database technology is not suitable for accomplishing the task, and new techniques need to be developed. In this dissertation, we propose several new techniques for discovering patterns in sequence databases. Our techniques incorporate pattern matching algorithms and novel heuristics for discovery and optimization. Experimental results of applying the techniques to both generated data and DNA/proteins show the effectiveness of the proposed techniques. We then develop several classifiers using our pattern discovery algorithms and a previously published fingerprint technique. When we apply the classifiers to classify DNA and protein seq...
A New Approach to Modeling Personal Office Documents.

Algorithms for Approximate Graph Matching.
Sequence databases comprise sequence data, which are linear structural descriptions of many natural entities. Approximate pattern discovery in a sequence database can lead to important conclusions or prediction of new phenomena. Traditional database technology is not suitable for accomplishing the task, and new techniques need to be developed. In this dissertation, we propose several new techniques for discovering patterns in sequence databases. Our techniques incorporate pattern matching algorithms and novel heuristics for discovery and optimization. Experimental results of applying the techniques to both generated data and DNA/proteins show the effectiveness of the proposed techniques. We then develop several classifiers using our pattern discovery algorithms and a previously published fingerprint technique. When we apply the classifiers to classify DNA and protein seq...
Document Management Through Hypertext A Logic Modeling Approach.
This work employs logic modeling as a common language to integrate two independent information domains-document management and hypertext. The concept of hypertext concerns information manage-ment and access. Hypertext can also be considered a knowledge representation that models the structure of the information system at serves. A hypertext en-gine would give the user flexible access to the infor-mation and commands of the underlying application, tailored to that applicatiov’s structure. This paper fo-cuses on integrating hypertext functionalities into an intelligent personal document processing system called TEXPROS. We develop independent logic data mod-els for hypertext and TEXPROS elements, and then present the logical representation of the bridge laws that map between them. We found logic modeling an invaluable tool in understanding our two domains and eflecting their integration. 1
A Knowledge%2DBased Tutoring System for SQL Programming.

Combinatorial Pattern Discovery for Scientific Data Some Preliminary Results.
Sequence databases comprise sequence data, which are linear structural descriptions of many natural entities. Approximate pattern discovery in a sequence database can lead to important conclusions or prediction of new phenomena. Traditional database technology is not suitable for accomplishing the task, and new techniques need to be developed. In this dissertation, we propose several new techniques for discovering patterns in sequence databases. Our techniques incorporate pattern matching algorithms and novel heuristics for discovery and optimization. Experimental results of applying the techniques to both generated data and DNA/proteins show the effectiveness of the proposed techniques. We then develop several classifiers using our pattern discovery algorithms and a previously published fingerprint technique. When we apply the classifiers to classify DNA and protein seq...
Approximate Graph Matching Using Probabilistic Hill Climbing Algorithms.
Sequence databases comprise sequence data, which are linear structural descriptions of many natural entities. Approximate pattern discovery in a sequence database can lead to important conclusions or prediction of new phenomena. Traditional database technology is not suitable for accomplishing the task, and new techniques need to be developed. In this dissertation, we propose several new techniques for discovering patterns in sequence databases. Our techniques incorporate pattern matching algorithms and novel heuristics for discovery and optimization. Experimental results of applying the techniques to both generated data and DNA/proteins show the effectiveness of the proposed techniques. We then develop several classifiers using our pattern discovery algorithms and a previously published fingerprint technique. When we apply the classifiers to classify DNA and protein seq...
DocFlow an event%2Ddriven visual programming environment for office automation through document processing.

Combinatorial Pattern Discovery for Scientific Data Some Preliminary Results.
Sequence databases comprise sequence data, which are linear structural descriptions of many natural entities. Approximate pattern discovery in a sequence database can lead to important conclusions or prediction of new phenomena. Traditional database technology is not suitable for accomplishing the task, and new techniques need to be developed. In this dissertation, we propose several new techniques for discovering patterns in sequence databases. Our techniques incorporate pattern matching algorithms and novel heuristics for discovery and optimization. Experimental results of applying the techniques to both generated data and DNA/proteins show the effectiveness of the proposed techniques. We then develop several classifiers using our pattern discovery algorithms and a previously published fingerprint technique. When we apply the classifiers to classify DNA and protein seq...
A System for Approximate Tree Matching.
Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology, programming compilation and natural language processing. Many of the applications involve comparing trees or retrieving/extracting information from a repository of trees. Examples include classification of unknown patterns, analysis of newly sequenced RNA structures, semantic taxonomy for dictionary definitions, generation of interpreters for nonprocedural programming languages, and automatic error recovery and correction for programming languages. Previous systems use exact matching (or generalized regular expression matching) for tree comparison. This paper presents a system, called Approximate-Tree-By-Example (ATBE), which allows inexact matching of trees. The ATBE system interacts with the user through a simple, but powerful query language; graphical devices a...
Exact and approximate algorithms for unordered tree matching.

Approximate Tree Matching in the Presence of Variable Length Don%27t Cares.
Ordered labeled trees are trees in which the sibling order matters. This paper presents algorithms  for three problems having to do with approximate matching for such trees with variable-length don&#039;t  cares (VLDC&#039;s).  In strings, a VLDC symbol in the pattern may substitute for zero or more symbols in the data  string. For example, if &#034;comer&#034; is the pattern, then the &#034;&#034; would substitute for the substring &#034;put&#034;  when matching the data string &#034;computer&#034;. Approximate VLDC matching in strings means that after  the best possible substitution, the pattern still need not be the same as the data string for a match  to be allowed. For example, &#034;comer&#034; matches &#034;counter&#034; within distance 1 (representing the cost of  removing the &#034;m&#034; from &#034;comer&#034; and having the &#034;&#034; substitute for &#034;unt&#034;).  We generalize approximate VLDC string matching to three algorithms for approximate VLDC  matching on trees. The time complexity of our algorithms is O(jP j \Theta jDj \Theta min(depth(P ); leaves(P )) \Theta  min(de...
A formal approach to modeling office information systems.

A Tool for Classifying Office Documents.

An OI5ce Document Retrieval System with the Capability of Processing Incomplete and Vague Queries.

An Intelligent Documentation Support Environment.

On research issues regarding uncertain query processing in an office document retrieval system.

Fast Serial and Parallel Algorithms for Approximate Tree Matching with VLDC%27s.
Ordered, labeled trees are trees in which each node has a label and the left-to-right order of its children (if it has any) is fixed. Such trees have many applications in vision, pattern recognition, molecular biology, programming compilation and natural language processing. Many of the applications involve comparing trees or retrieving/extracting information from a repository of trees. Examples include classification of unknown patterns, analysis of newly sequenced RNA structures, semantic taxonomy for dictionary definitions, generation of interpreters for nonprocedural programming languages, and automatic error recovery and correction for programming languages. Previous systems use exact matching (or generalized regular expression matching) for tree comparison. This paper presents a system, called Approximate-Tree-By-Example (ATBE), which allows inexact matching of trees. The ATBE system interacts with the user through a simple, but powerful query language; graphical devices a...
Pattern Matching in Unordered Trees.

Texpros an Intelligent Document Processing System.

Optimizing Equijoin Queries In Distributed Databases Where Relations Are Hash Partitioned.
Consider the class of distributed database systems consisting of a set of nodes connected by a high bandwidth network. Each node consists of a processor, a random access memory, and a slower but much larger memory such as a disk. There is no shared memory among the nodes. The data are horizontally partitioned often using a hash function. Such a description characterizes many parallel or distributed database systems that have recently been proposed, both commercial and academic. We study the optimization problem that arises when the query processor must repartition the relations and intermediate results participating in a multijoin query. Using estimates of the sizes of intermediate relations, we show (1) optimum solutions for closed chain queries; (2) the NP-completeness of the optimization problem for star, tree, and general graph queries; and (3) effective heuristics for these hard cases. Our general approach and many of our results extend to other attribute partitioning schemes, for example, sort-partitioning on attributes, and to partitioned object databases.
Query Processing for Distance Metrics.
In applications such as vision and molecular biology, a common problem is to find the similar objects to a given target (according to some distance measure) in a large database. This paper presents a scheme for query pro-cessing in such situations. The basic strategy is to (par-tially) precompute inter-object distances, and by using the distance information and the triangle inequality, we eliminate the need to calculate certain object distances while evaluating queries. We propose several heuristics that may speed up query evaluation. A series of experi-ments are then performed to evaluate the effectiveness of our scheme and the relative performance of the heuristics for different queries. Finally we investigate the possibil-ity of parallelizing our scheme through simulation. Our results show that parallelism is best applied in the later stages in evaluating a query. 1
New Techniques for Best%2DMatch Retrieval.
A scheme to answer best-match queries from a file containing a collection of objects is described. A best-match query is to find the objects in the file that are closest (according to some (dis)similarity measure) to a given target. Previous work [5, 331 suggests that one can reduce the number of comparisons required to achieve the desired results using the triangle inequality, starting with a data structure for the file that reflects some precomputed intrafile distances. We generalize the technique to allow the optimum use of any given set of precomputed intrafile distances. Some empirical results are presented which illustrate the effectiveness of our scheme, and its performance relative to previous algorithms.
